package LeetCode;

import java.util.ArrayList;
import java.util.List;

public class LC_442_FindAllDuplicatesinanArray {

    public static void main(String[] args) {

    }

    public class Solution {
        public List<Integer> findDuplicates(int[] nums) {
            List<Integer> result = new ArrayList<>();
            int len = nums.length;
            int n = len;
            for (int i = 0; i < len; i++) {
                int num = nums[i] % n == 0 ? n : nums[i] % n;
                nums[num - 1] += len;
            }

            for (int i = 0; i < len; i++) {
                if (nums[i] > 2 * n) {
                    result.add(i + 1);
                }
            }
            return result;
        }

    }
}